1. FINITE AUTOMATA, REGULAR LANGUAGES, REGULAR GRAMMARS:
DETERMINISTIC VS. NONDETERMINISTIC, ONE-WAY VS. TWO-WAY FINITE AUTOMATA, MINIMIZATION,
PUMPING LEMMA FOR REGULAR SETS, CLOSURE PROPERTIES.
2. PUSHDOWN AUTOMATA, CONTEXT-FREE LANGUAGES, CONTEXT-FREE GRAMMARS:
DETERMINISTIC VS. NONDETERMINISTIC, ONE-WAY VS. TWO-WAY PDAS, REVERSAL BOUNDED PDAS,
LINEAR GRAMMARS, COUNTER MACHINES, PUMPING LEMMA FOR CFLS, CHOMSKY NORMAL FORM,
GREIBACH NORMAL FORM, CLOSURE PROPERTIES.
3. LINEAR BOUNDED AUTOMATA, CONTEXT-SENSITIVE LANGUAGES, CONTEXT-SENSITIVE GRAMMARS.
4. TURING MACHINES, RECURSIVELY ENUMERABLE SETS, TYPE 0 GRAMMARS:
VARIANTS OF TURING MACHINES, HALTING PROBLEM, UNDECIDABILITY, POST CORRESPONDENCE
PROBLEM, VALID AND INVALID COMPUTATIONS OF TMS.
5. BASIC RECURSIVE FUNCTION THEORY
6. BASIC COMPLEXITY THEORY:
VARIOUS RESOURCE BOUNDED COMPLEXITY CLASSES, INCLUDING NLOGSPACE, P, NP,
PSPACE, EXPTIME, AND MANY MORE. REDUCIBILITY, COMPLETENESS.
7. ADVANCED TOPICS IN COMPLEXITY THEORY:
APPROXIMATION ALGORITHMS, PROBABILISTIC COMPLEXITY, PARALLEL COMPLEXITY, ALTERNATION,
INTERACTIVE PROOF SYSTEMS, ORACLE COMPUTATIONS.